51. N-Queens
Hard

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

 

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [["Q"]]

 

Constraints:

  • 1 <= n <= 9
Accepted
275,452
Submissions
527,294
Seen this question in a real interview before?
Companies
Related Topics
Similar Questions

Average Rating: 4.81 (26 votes)

Premium

Solution


Overview

A brute force solution would involve generating all possible board states with N queens. There are N2N^2 possible squares to place the first queen, N21N^2 - 1 to place the second and so on. This leads to a time complexity of O(N2N)O(N^{2N}), which is far too slow. The actual number of solutions is far fewer than the number of possible board states, so we should aim to minimize our consideration of invalid board states.

Imagine if we tried to generate all board states by placing queens down one by one. For 8 queens on a normal chessboard, let's say we place the first queen on the top left (index (0, 0), or, if you are familiar with Chess, a8). Then, we place the second queen to its right (index (0, 1), or b8).


There are 62 * 61 * ... * 57 = 44,261,653,680 possible ways to place the remaining 6 queens, but we already know that every single one of them is invalid, because the first 2 queens can attack each other.



Approach: Backtracking

Intuition

We can still follow the strategy of generating board states, but we should never place a queen on a square that another queen can attack. This is a perfect problem for backtracking - place the queens one by one, and when all possibilities are exhausted, backtrack by removing a queen and placing it elsewhere.

If you're not familiar with backtracking, check out the backtracking section of our Recursion II Explore Card.

Given a board state, and a possible placement for a queen, we need a smart way to determine whether or not that placement will put the queen under attack. A queen can be attacked if another queen is on the same row, column, diagonal, or anti-diagonal.

Recall that to implement backtracking, we implement a backtrack function that makes some changes to the state, calls itself again, and then when that call returns it undoes those changes (this last part is why it's called "backtracking").

Each time our backtrack function is called, we can encode the state in the following manner:

  • To make sure that we only place 1 queen per row, we will pass an integer argument row into backtrack, and will only place one queen during each call. Whenever we place a queen, we'll move onto the next row by calling backtrack again with the parameter value row + 1.

  • To make sure we only place 1 queen per column, we will use a set. Whenever we place a queen, we can add the column index to this set.

The diagonals are a little trickier - but they have a property that we can use to our advantage.

  • For each square on a given diagonal, the difference between the row and column indices (row - col) will be constant. Think about the diagonal that starts from (0, 0) - the ithi^{th} square has the coordinates (i, i), so the difference is always 0.


  • For each square on a given anti-diagonal, the sum of the row and column indexes (row + col) will be constant. If you were to start at the highest square in an anti-diagonal and move downwards, the row index increments by 1 (row + 1), and the column index decrements by 1 (col - 1). These cancel each other out.


Every time we place a queen, we should calculate the diagonal and the anti-diagonal value it belongs to. In the same way we use a set to keep track of which columns have been used, we should also have a set to keep track of which diagonals and anti-diagonals have been used. Then, we can add the values for this queen to the corresponding sets.

Algorithm

We'll create a recursive function backtrack that takes a few arguments to maintain the board state. The first parameter is the row we're going to place a queen on next, and then we will have 3 sets that track which columns, diagonals, and anti-diagonals have already had queens placed on them. Additionally, we will store the actual board so that when we find a valid solution, we can include it in our answer. The function will work as follows:

  1. If the current row we are considering is equal to n, then we have a solution. Add the current board state to a list of solutions, and return. We'll make use of a small helper function to get our board into the correct output format.

  2. Iterate through the columns of the current row. At each column, we will attempt to place a queen at the square (row, col) - remember we are considering the current row through the function arguments.

    • Calculate the diagonal and anti-diagonal that the square belongs to. If a queen has not been placed in the column, diagonal, or anti-diagonal, then we can place a queen in this column, in the current row.
    • If we can't place the queen, skip this column (move on and try the next column).
  3. If we were able to place a queen, then add the queen to the board and update our 3 sets (cols, diagonals, and antiDiagonals), and call the function again, but with row + 1.

  4. The function call made in step 3 explores all valid board states with the queen we placed in step 2. Since we're done exploring that path, backtrack by removing the queen from the square - this includes removing the values we added to our sets on top of removing the "Q" from the board.

Implementation

Complexity Analysis

Given NN as the number of queens (which is the same as the width and height of the board),

  • Time complexity: O(N!)O(N!)

    Unlike the brute force approach, we will only place queens on squares that aren't under attack. For the first queen, we have NN options. For the next queen, we won't attempt to place it in the same column as the first queen, and there must be at least one square attacked diagonally by the first queen as well. Thus, the maximum number of squares we can consider for the second queen is N2N - 2. For the third queen, we won't attempt to place it in 2 columns already occupied by the first 2 queens, and there must be at least two squares attacked diagonally from the first 2 queens. Thus, the maximum number of squares we can consider for the third queen is N4N - 4. This pattern continues, resulting in an approximate time complexity of N!N!.

    While it costs O(N2)O(N^2) to build each valid solution, the amount of valid solutions S(N)S(N) does not grow nearly as fast as N!N!, so O(N!+S(N)N2)=O(N!)O(N! + S(N) * N^2) = O(N!)

  • Space complexity: O(N2)O(N^2)

    Extra memory used includes the 3 sets used to store board state, as well as the recursion call stack. All of this scales linearly with the number of queens. However, to keep the board state costs O(N2)O(N^2), since the board is of size N * N. Space used for the output does not count towards space complexity.



Report Article Issue

Comments: 11
jca88's avatar
Read More

good article for a classic hard problem that should always be in our back pocket! to be honest, I was scared of even attempting this problem! but the write up helped a lot! thank you!

5
Reply
Share
Report
here-comes-the-g's avatar
Read More

one of the rarest occasion of seeing a cleaner/readable code in solution section rather than from the discuss section.
great article.

4
Reply
Share
Report
kishorekumar21's avatar
Read More

O(n) Space solution:

class Solution {
    private boolean[] visitedCols;
    boolean[] visitedDiag, visitedAntiDiag;
    private List<List<String>> solutionBoards;
    private int[] queenPositions;
    
    public List<List<String>> solveNQueens(int n) {
        visitedCols = new boolean[n];
        visitedDiag = new boolean[n << 1];
        visitedAntiDiag = new boolean[n << 1];
        
        queenPositions = new int[n];
        solutionBoards = new ArrayList<>();
        
        backtrack(n, 0);
        
        return solutionBoards;
    }
    
    private void backtrack(int n, int row){
        if(row == n){
            fillSolutionBoard(n);
        }
        
        for(int col=0; col<n; col++){
            if(!visitedCols[col]
               && !isDiagonalsVisited(row, col, n)){
                queenPositions[row] = col;
                if(row == n-1){
                    fillSolutionBoard(n);
                    continue;
                }
                
                visitedCols[col] = true;
                markDiagonals(row, col, true, n);
                
                backtrack(n, row+1);
                
                queenPositions[row] = -1;
                visitedCols[col] = false;
                markDiagonals(row, col, false, n);
            }
        }
    }
    
    private boolean isDiagonalsVisited(int row, int col, int n){
        int diag = row - col + (n-1);
        int antiDiag = row + col;
        return visitedDiag[diag] || visitedAntiDiag[antiDiag];
    }
    
    private void markDiagonals(int row, int col, boolean isVisit, int n){
        int diag = row - col + (n-1);
        int antiDiag = row + col;
        visitedDiag[diag] = isVisit;
        visitedAntiDiag[antiDiag] = isVisit;
    }
    
    private void fillSolutionBoard(int n){
        List<String> solBoard = new ArrayList<>();
        StringBuilder row = new StringBuilder();
        for(int i=0; i<n; i++)
            row.append('.');
        for(int q=0; q<n; q++){
            row.setCharAt(queenPositions[q], 'Q');
            solBoard.add(row.toString());
            row.setCharAt(queenPositions[q], '.');
        }
        
        solutionBoards.add(solBoard);
    }
}

2
Reply
Share
Report
allaroundboy's avatar
Read More

This solution is so easy-understanding and organized for the leetcode beginners!

0
Reply
Share
Report
bubuzu's avatar
Read More

I have real O(N) solution. (it's Kotlin)

  • One int array
  • Recursion with N steps deep
fun solveNQueens(n: Int): List<List<String>> {
    val result = mutableListOf<MutableList<String>>()
    val qs = IntArray(n)

    fun move(x: Int, y: Int) {
        for (i in 0 until x) {
            if (qs[i] == y || x - i == Math.abs(qs[i] - y)) return
        }
        qs[x] = y
        if (x != n - 1) {
            for (i in 0 until n) {
                move(x + 1, i)
            }
        } else {
            result.add(MutableList(n) { i -> String(CharArray(n) { y -> if (qs[i] == y) 'Q' else '.' }) })
        }
    }

    for (j in 0 until n) {
        move(0, j)
    }

    return result
}

0
Show 1 reply
Reply
Share
Report
Yinyu78's avatar
Read More

The diagonal and anti-diagonal values don't need to be kept in sets - a single unordered set or vector is enough; the (anti-)diagonal can be deduced by column[row] -/+ row.

0
Reply
Share
Report
sriharik's avatar
Read More

Calculating the diagonal and antidiagonal values is actually really smart. I thought I would have to do a DFS to see if the queen attacked another queen.

0
Reply
Share
Report
yuhan-wang's avatar
Read More

I don't agree with the time complexity analysis. The backtracking algorithm doesn't just consider the correct solutions- if you look at the for loop in line17 of the python3 solution, even when the queen is not placeable, that wrong state is still considered (even though we stop our backtracking). As an example of the argument, for each correct solution, we have to reach the last row where we also consider every other column of this last row in the backtracking algorithm.
That being said, it might still be correct the time complexity is O(n!), it's just the argument is not O(correct number of solutions) and therefore O(n!).

0
Show 3 replies
Reply
Share
Report
jinkim's avatar
Read More

is this an NP problem?

0
Reply
Share
Report
williamtan37's avatar
Read More

Really good explanation!

0
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
05/22/2021 12:53Accepted4 ms7.1 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.